from typing import *


class Solution:
    def minIncrements(self, n: int, cost: List[int]) -> int:
        mx = [0] * n
        sm = [0] * n
        for i in range(n - 1, -1, -1):
            id, c = i + 1, cost[i]
            pid = id // 2 - 1
            sm[i] += c
            mx[i] += c
            if pid > -1:
                sm[pid] += c
                mx[pid] = max(mx[pid], mx[i])
        ans = 0
        rest = [0] * n
        rest[0] = mx[0]
        for i in range(n):
            id, c = i + 1, cost[i]
            l, r = id * 2 - 1, id * 2
            add = rest[i] - max(mx[l] if l < n else 0, mx[r] if r < n else 0) - c
            ans += add
            if l < n:
                rest[l] = rest[i] - add - c
            if r < n:
                rest[r] = rest[i] - add - c
        return ans


s = Solution()
print(s.minIncrements(n=7, cost=[1, 5, 2, 2, 3, 3, 1]))
# print(s.minIncrements(n=3, cost=[5, 3, 3]))
